package util.adt;

import interview.aug1022.Tree;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Zefeng Wang
 */
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode() {
    }

    public TreeNode(int val) {
        this.val = val;
    }

    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    public static TreeNode buildFromArray(Integer[] array) {
        if (array == null || array.length == 0 || array[0] == null) {
            return null;
        }
        TreeNode root = new TreeNode(array[0]);
        List<TreeNode> currentLayer = new ArrayList<>();
        currentLayer.add(root);
        int i = 1;
        while (i < array.length) {
            List<TreeNode> newLayer = new ArrayList<>();
            for (TreeNode node : currentLayer) {
                Integer left = array[i];
                i++;
                if (i == array.length) {
                    break;
                }
                Integer right = array[i];
                i++;
                if (i == array.length) {
                    break;
                }
                if (left != null) {
                    TreeNode leftNode = new TreeNode(left);
                    node.left = leftNode;
                    newLayer.add(leftNode);
                }
                if (right != null) {
                    TreeNode rightNode = new TreeNode(right);
                    node.right = rightNode;
                    newLayer.add(rightNode);
                }
            }
            currentLayer = newLayer;
        }
        return root;
    }

    @Override
    public String toString() {
        return "{" + val + "}";
    }
}
